#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"


//开辟
ListNode* BuyListNode(LTDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

//初始化
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//释放
//清理所有数据结点，保留头结点，可以继续使用
void ListClear(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur=next;
	}
	//保持头结点(带头双向循环)
	phead->next = phead;
	phead->prev = phead;
}

//整个给销毁
void ListDestory(ListNode** pphead)
{
	assert(*pphead);
	ListClear(*pphead);
	free(*pphead);
	*pphead = NULL;
}


//打印
ListNode* ListPrint(ListNode* phead)
{
	assert(phead);
	//因为phead不是有效值（哨兵）
	//所以打印应该是从第二个结点开始
	ListNode* cur = phead->next;
	//然后走到最后一结点（一圈）之后不等于phead时为一循环
	while (cur != phead) 
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);

	/*ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	phead ->prev = newnode;
	newnode->next = phead;*/
	//在头结点的前面插入就是尾插
	ListErase(phead->prev, x);

}

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	//下面的assert是断言为了避免删除了头结点
	assert(phead->next != phead);
	/*ListNode* tail = phead->prev;
	ListNode* tailprev = tail->prev;
	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
	tail = NULL;*/
	//在头结点的前面删除就是尾删
	ListErase(phead->prev);
}

//头插
void ListPushPront(ListNode* phead, LTDataType x)
{
	assert(phead);
	/*ListNode* headprev = BuyListNode(x);
	ListNode* head = phead->next;
	headprev->next = head;
	head->prev = headprev;
	phead->next = headprev;
	headprev->prev = phead;*/

	//在头结点下一个结点的前面插入就是头插
	ListInsert(phead->next, x);
}


//头删
void ListPopPront(ListNode* phead)
{
	assert(phead);
	//下面的assert是断言为了避免删除了头结点
	assert(phead->next != phead);
	/*ListNode* head = phead->next;
	ListNode* next = head->next;
	phead->next = next;
	next->prev = phead;
	free(head);*/
	//在头结点下一个结点的前面删除就是头删
	ListErase(phead->next);
}


//在pos前面插入x
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}


//删除pos前的结点
void ListErase(ListNode* pos)
{
	assert(pos);
	//不可以删头（哨兵）
	//assert(pos != phead);
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}